// 132.分割回文串2
package Leetcode_Second_Brush;

public class Solution132 {
    public int minCut(String s) {
        int length = s.length();
        boolean[][] dp = new boolean[length][length];

        // Initialize the dp array for single characters and fill for substrings
        for (int end = 0; end < length; end++) {
            for (int start = 0; start <= end; start++) {
                if (s.charAt(start) == s.charAt(end) && (end - start <= 2 || dp[start + 1][end - 1])) {
                    dp[start][end] = true;
                }
            }
        }

        // f[i] 表示 s[0~i] 的最小分割次数
        int[] f = new int[length];
        for (int i = 0; i < length; i++) {
            if (dp[0][i]) {
                f[i] = 0;
            } else {
                f[i] = i; // 最多切割 i 次 (每个字符单独切割)
                for (int j = 1; j <= i; j++) {
                    if (dp[j][i]) {
                        f[i] = Math.min(f[i], f[j - 1] + 1);
                    }
                }
            }
        }

        return f[length - 1];
    }
}
